//=============================================================================
//      $Id: dynamic_array.cpp 225 2013-01-04 11:45:42Z sergey.kazenyuk@gmail.com $
//      $URL: http://spbau-cpp-2011.googlecode.com/svn/trunk/kazenyuk/hw01_dynamic-array/src/dynamic_array.cpp $
//=============================================================================

#include <iostream>
#include <cstddef>
#include <stdexcept>
#include <algorithm>
#include <cassert>

template <typename T>
class DynamicArray
{
public:
	DynamicArray();
	explicit DynamicArray(size_t capacity, size_t front_slack_size = 0);
	DynamicArray(const DynamicArray &array);
	~DynamicArray();	
	DynamicArray &operator=(const DynamicArray<T> &array);
	
	
	size_t size() const;
	size_t capacity() const;
	bool empty() const;
	
	const T &get(size_t index) const;
	void set(size_t index, const T &value);
	
	void push_back(const T &value);
	void pop_back();
	T back() const;
	void push_front(const T &value);
	void pop_front();
	T front() const;
	
	void clear();
	void reserve(size_t reserve_size);
	void swap(DynamicArray<T> &array);
	
#if defined(_DEBUG)
	void std_out() const;
#endif

protected:
#if defined(_DEBUG)
	void print_state() const;
#endif
	void reserve(size_t reserve_size, int start_index);
	size_t free_at_front() const;
	size_t free_at_back() const;

private:
	size_t m_size;
	size_t m_capacity;
	T *m_mem;
	T *m_data;
};

template <typename T>
DynamicArray<T>::DynamicArray()
	:m_size(0), m_capacity(0), m_mem(NULL), m_data(m_mem)
{}

template <typename T>
DynamicArray<T>::DynamicArray(size_t capacity, size_t front_slack_size)
	:m_size(0), m_capacity(capacity), m_mem(new T[capacity]), 
	m_data(m_mem+front_slack_size)
{}

template <typename T>
DynamicArray<T>::DynamicArray(const DynamicArray<T> &array)
{
	m_mem = new T[array.m_capacity];
	m_data = m_mem + (array.m_data-array.m_mem);
	m_capacity = array.m_capacity;
	m_size = array.m_size;
	std::copy(array.m_data, array.m_data + array.m_size, m_data);
	
#if defined(_DEBUG)
	print_state();
#endif
}

template <typename T>
DynamicArray<T>::~DynamicArray()
{
	delete[] m_mem;
}

template <typename T>
DynamicArray<T> &DynamicArray<T>::operator=(const DynamicArray<T> &array)
{	
	DynamicArray<T> temp(array);
	temp.swap(*this);
	
#if defined(_DEBUG)
	print_state();
#endif
	return *this;
}

template <typename T>
size_t DynamicArray<T>::size() const
{
	return m_size;
}

template <typename T>
size_t DynamicArray<T>::capacity() const
{
	return m_capacity;
}
	
template <typename T>
bool DynamicArray<T>::empty() const
{
	return m_size == 0;
}

template <typename T>
const T &DynamicArray<T>::get(size_t index) const
{
	if (index < m_size)
	{
		return m_data[index];
	}
	throw std::out_of_range("DynamicArray index out of bounds");
}

template <typename T>
void DynamicArray<T>::set(size_t index, const T &value)
{
	if (index < m_size)
	{
		m_data[index] = value;
	}
	throw std::out_of_range("DynamicArray index out of bounds");
}

template <typename T>
void DynamicArray<T>::push_back(const T &value)
{
	if (m_size+1 >= m_capacity)
	{
		reserve(size_t(m_capacity*1.5+1));
	}
	m_data[m_size++] = value;
#if defined(_DEBUG)
	std::cout << "push_back ";
	print_state();
#endif
}

template <typename T>
void DynamicArray<T>::pop_back()
{
	if (m_size > 0)
	{
		--m_size;
	}
#if defined(_DEBUG)
	std::cout << "pop_back ";
	print_state();
#endif
}

template <typename T>
T DynamicArray<T>::back() const
{
	if (m_size > 0)
	{
		return m_data[m_size-1];
	}
	throw std::out_of_range("DynamicArray index out of bounds");
}

template <typename T>
void DynamicArray<T>::push_front(const T &value)
{
	if (free_at_front() == 0)
	{
		reserve(size_t(m_capacity*0.5+m_capacity*1.5+1), size_t(m_capacity*0.5));
	}
	
	--m_data;
	++m_size;
	m_data[0] = value;
	
#if defined(_DEBUG)
	std::cout << "push_front ";
	print_state();
#endif
}

template <typename T>
void DynamicArray<T>::pop_front()
{
	if (m_size > 0)
	{
		--m_size;
		++m_data;
	}
#if defined(_DEBUG)
	std::cout << "pop_front ";
	print_state();
#endif
}

template <typename T>
T DynamicArray<T>::front() const
{
	if (m_size > 0)
	{
		return m_data[0];
	}
	throw std::out_of_range("DynamicArray index out of bounds");
}

template <typename T>
void DynamicArray<T>::clear()
{
	m_size = 0;
	//TODO: destructor should be called here
}

template <typename T>
void DynamicArray<T>::reserve(size_t reserve_size)
{
	reserve(reserve_size, 0);
}

template <typename T>
void DynamicArray<T>::reserve(size_t reserve_size, int data_offset)
{
	assert(reserve_size >= m_capacity);
	assert(data_offset < static_cast<int>(reserve_size-m_size));
	
	DynamicArray<T> temp(reserve_size);
	temp.m_data = temp.m_mem + (m_data-m_mem) + data_offset;
	temp.m_size = m_size;
	std::copy(m_data, m_data + m_size, temp.m_data);
	temp.swap(*this);
	
#if defined(_DEBUG)
	std::cout << "reserve ";
	print_state();
#endif
}

template <typename T>
void DynamicArray<T>::swap(DynamicArray<T> &array)
{
	std::swap(m_size, array.m_size);
	std::swap(m_capacity, array.m_capacity);
	std::swap(m_mem, array.m_mem);
	std::swap(m_data, array.m_data);
}

template <typename T>
size_t DynamicArray<T>::free_at_front() const
{
	return m_data-m_mem;
}

template <typename T>
size_t DynamicArray<T>::free_at_back() const
{
	return m_mem+m_capacity-m_data-m_size;
}

#if defined(_DEBUG)
template <typename T>
void DynamicArray<T>::std_out() const
{
	for (size_t i=0; i<capacity(); ++i)
	{
		std::cout << m_mem[i] << " ";	
	}
	std::cout << std::endl;
}

template <typename T>
void DynamicArray<T>::print_state() const
{
	std::cout << "DynamicArray: m_size=" << m_size 
				<< " m_capacity=" << m_capacity 
				<< std::hex
				<< " m_mem=[" << reinterpret_cast<intptr_t>(m_mem) 
				<< ";" << reinterpret_cast<intptr_t>(m_mem+m_capacity) << "]"
				<< " m_data=[" << reinterpret_cast<intptr_t>(m_data) 
				<< ";" << reinterpret_cast<intptr_t>(m_data+m_size) << "]"
				<< " free_at_front=" << free_at_front() 
				<< " free_at_back=" << free_at_back()
				<< " front_slack=[" << reinterpret_cast<intptr_t>(m_mem) 
				<< ";" << reinterpret_cast<intptr_t>(m_mem+free_at_front()) << "]"
				<< " back_slack=[" << reinterpret_cast<intptr_t>(m_data+m_size) 
				<< ";" << reinterpret_cast<intptr_t>(m_data+m_size+free_at_back()) << "]"
				<< std::dec
				<< std::endl;
}
#endif

int main(int argc, char **argv)
{
	size_t arr_capacity = 10;
	size_t arr_elems_to_add = 15;
	DynamicArray<int> arr(arr_capacity);
	
	std::cout << "gen: ";
	for (size_t i=0; i<arr_elems_to_add; ++i)
	{
		int new_elem = rand()%(arr_elems_to_add+1);
		std::cout << new_elem << " ";
		arr.push_back(new_elem);
#if defined(_DEBUG)
		arr.std_out();
#endif
	}
	std::cout << std::endl;

#if defined(_DEBUG)
	arr.std_out();
#endif
	
	DynamicArray<int> b(arr);
#if defined(_DEBUG)
	b.std_out();
#endif
	
	DynamicArray<int> c;
	c = b;
#if defined(_DEBUG)
	c.std_out();
#endif
	
	DynamicArray<int> d;
	d = b;
#if defined(_DEBUG)
	d.std_out();
#endif
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_back(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_back(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_back(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
	d.push_back(rand()%(arr_elems_to_add+1));
	d.push_front(rand()%(arr_elems_to_add+1));
#if defined(_DEBUG)
	d.std_out();
#endif
	
	try
	{
		c.get(c.size()+1);
	}
	catch (std::out_of_range &e)
	{
		std::cout << "Exception catched: " << e.what() << std::endl;
	}
	
	try
	{
		c.set(c.size()+1, 0xDEAD);
	}
	catch (std::out_of_range &e)
	{
		std::cout << "Exception catched: " << e.what() << std::endl;
	}
	
	return 0;
}
